// ProiectPreflux.cpp : Defines the entry point for the application.
//

#include "stdafx.h"
#include "ProiectPreflux.h"
#include <string.h>
#include <cmath>
#include <cstdlib>
#include <Commdlg.h>
#include <stdio.h>

#define MAX_LOADSTRING 100

// Global Variables:
HINSTANCE hInst;								// current instance
TCHAR szTitle[MAX_LOADSTRING];					// The title bar text
TCHAR szWindowClass[MAX_LOADSTRING];			// the main window class name
OPENFILENAME ofn;
TCHAR szFileName[MAX_PATH] = L"";
char FileName[MAX_PATH];
FILE *f;
char numeR[32],c4[32];
TCHAR c1[20]=L"",c3[32]=L"",c2[32]=L"";

//Variabile Butoane
bool bDrawNod=false,bAdaugaMuchie=false,bDrawAgain=false,bDrawOras=false;
bool random1Draw=false,random2Draw=false,random3Draw=false;

//Indice noduri
int IndNod=0;
LARGE_INTEGER frequency;        
LARGE_INTEGER t1, t2,t3,t4,t5,t6;           
double elapsedTime1,elapsedTime2,elapsedTime3;
char milisec[sizeof(elapsedTime1)];




//sursa si destinatia

char sursa[32],dest[32];

//Principalele structuri de date

typedef struct muchieCant{
	char c[20];
	int cant;
	int flux;
	muchieCant *next;
}muchieCant;

typedef struct nod{
	int x;// coordonatele nodului
	int y;
	char nume[20];
	muchieCant *p;
	int h;//inaltimea la care se afla nodul
	int e;//cantitatea reziduala
}nod;


//Declararea vectorului de noduri

nod graf[5000];
char **vec;



// Forward declarations of functions included in this code module:
ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK	About(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK	NumeOras(HWND , UINT , WPARAM , LPARAM );
INT_PTR CALLBACK	SursaDestinatie(HWND , UINT , WPARAM , LPARAM );
INT_PTR CALLBACK	Muchie(HWND , UINT , WPARAM , LPARAM );
void				AdaugaNod(int ,int );
void				DrawCity(HDC ,int ,int ,char* );
void				DrawLine(HDC ,int ,int ,int ,int,int );
void				DrawGraph(HDC,int ,int ,int ,int, TCHAR *,int ,int ,int);
void				InitInaltime(char* ,int );
int					SearchIndice(char* ,int );
bool				SearchMuchie(nod ,char* ,int );
int					CostMinim(char* ,char* ,int );
void				InitializarePref(char* ,int );
void				free2(int);
void				Pompare(char* ,char* ,int );
void				Inaltare(char* ,int );
void				PomparePref(char* ,char* ,int );
int					RealPreflow(char* ,char* , int );
void				CreareMuchii(int );
int					CitireRandom(int );
int					Random1( );
int					Random2( );
int					Random3( );
int					exemplu( );
void				free1();
void				CreateNods();

int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
	UNREFERENCED_PARAMETER(hPrevInstance);
	UNREFERENCED_PARAMETER(lpCmdLine);

 	// TODO: Place code here.
	MSG msg;
	HACCEL hAccelTable;
	vec=(char**)malloc(1000*sizeof(char*));

	// Initialize global strings
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_PROIECTPREFLUX, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);

	// Perform application initialization:
	if (!InitInstance (hInstance, nCmdShow))
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_PROIECTPREFLUX));

	// Main message loop:
	while (GetMessage(&msg, NULL, 0, 0))
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}

	return (int) msg.wParam;
}



//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
//  COMMENTS:
//
//    This function and its usage are only necessary if you want this code
//    to be compatible with Win32 systems prior to the 'RegisterClassEx'
//    function that was added to Windows 95. It is important to call this function
//    so that the application will get 'well formed' small icons associated
//    with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX);

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, MAKEINTRESOURCE(IDI_PROIECTPREFLUX));
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= MAKEINTRESOURCE(IDC_PROIECTPREFLUX);
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

	return RegisterClassEx(&wcex);
}

//
//   FUNCTION: InitInstance(HINSTANCE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // Store instance handle in our global variable

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, SW_MAXIMIZE);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  PURPOSE:  Processes messages for the main window.
//
//  WM_COMMAND	- process the application menu
//  WM_PAINT	- Paint the main window
//  WM_DESTROY	- post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent,kil,a;
	bool pos=false;
	PAINTSTRUCT ps;
	HDC hdc;
	HWND hWndButton1,hWndButton2,hWndButton3,hWndButton4,hWndButton5,hWndButton6,hWndButton7,hWndButton8,hWndButton9;
	int iPosX,iPosY;
	char nume[20];
 
    QueryPerformanceFrequency(&frequency);
	switch (message)
	{
	case WM_CREATE:
		hWndButton3=CreateWindowEx(NULL, L"BUTTON",L"Adauga Oras",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,10,150,24,hWnd,(HMENU)IDC_DRAW_NOD,GetModuleHandle(NULL),NULL);
		hWndButton1=CreateWindowEx(NULL, L"BUTTON",L"Adauga Muchie",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,34,150,24,hWnd,(HMENU)IDC_ADAUGA_MUCHIE,GetModuleHandle(NULL),NULL);
		hWndButton2=CreateWindowEx(NULL, L"BUTTON",L"Deseneaza din nou",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,58,150,24,hWnd,(HMENU)IDC_DRAW_AGAIN,GetModuleHandle(NULL),NULL);
		hWndButton4=CreateWindowEx(NULL, L"BUTTON",L"Calculeaza Flux",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,82,150,24,hWnd,(HMENU)IDC_PREFLUX,GetModuleHandle(NULL),NULL);
		hWndButton5=CreateWindowEx(NULL, L"BUTTON",L"Sursa Destinatie",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,106,150,24,hWnd,(HMENU)IDC_SURSA,GetModuleHandle(NULL),NULL);
		hWndButton6=CreateWindowEx(NULL, L"BUTTON",L"Random 1",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,130,150,24,hWnd,(HMENU)IDC_RANDOM1,GetModuleHandle(NULL),NULL);
		hWndButton7=CreateWindowEx(NULL, L"BUTTON",L"Random 2",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,154,150,24,hWnd,(HMENU)IDC_RANDOM2,GetModuleHandle(NULL),NULL);
		hWndButton8=CreateWindowEx(NULL, L"BUTTON",L"Random 3",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,178,150,24,hWnd,(HMENU)IDC_RANDOM3,GetModuleHandle(NULL),NULL);
		hWndButton9=CreateWindowEx(NULL, L"BUTTON",L"Exemplu",WS_TABSTOP|WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON,10,202,150,24,hWnd,(HMENU)IDC_EXEMPLU,GetModuleHandle(NULL),NULL);
		break;
	case WM_LBUTTONDOWN:
		for(int i=0;i<IndNod;i++){
			if(((LOWORD(lParam)>(graf[i].x-10))&&(LOWORD(lParam)<(graf[i].x+30)))&&((HIWORD(lParam)>(graf[i].y-10))&&(HIWORD(lParam)<(graf[i].y+30))))
				pos=true;
		}
		if(bDrawOras==true&&(!pos)){
			InvalidateRect(hWnd,0,TRUE);
			iPosX=LOWORD(lParam);
			iPosY=HIWORD(lParam);
			bDrawNod=true;
			graf[IndNod].y=iPosY;
			graf[IndNod].x=iPosX;
			IndNod++;
			bDrawOras=false;
		}
		break;
	case WM_COMMAND:
		wmId    = LOWORD(wParam);
		wmEvent = HIWORD(wParam);
		// Parse the menu selections:
		switch (wmId)
		{
		case IDM_ABOUT:
			DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
			break;
		case IDM_EXIT:
			DestroyWindow(hWnd);
			break;
		case IDC_DRAW_NOD:
			DialogBox(hInst,MAKEINTRESOURCE(IDD_DIALOG1),hWnd,NumeOras);
			InvalidateRect(hWnd,0,TRUE);
			break;
		case IDC_DRAW_AGAIN:
			bDrawAgain=true;
			InvalidateRect(hWnd,0,TRUE);
			free1();
			random1Draw=false;
			random2Draw=false;
			random3Draw=false;
			break;
		case IDC_RANDOM1:
			random1Draw=true;
			IndNod=0;
			QueryPerformanceCounter(&t1);
			kil=Random1();
			QueryPerformanceCounter(&t2);
			elapsedTime1 = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
			swprintf(c1,L"%f",elapsedTime1);
			InvalidateRect(hWnd,0,TRUE);
			free2(100);
			break;
		case IDC_RANDOM2:
			random2Draw=true;
			QueryPerformanceCounter(&t3);
			kil=Random2();
			QueryPerformanceCounter(&t4);
			elapsedTime2 = (t4.QuadPart - t3.QuadPart) * 1000.0 / frequency.QuadPart;
			swprintf(c2,L"%f",elapsedTime2);
			InvalidateRect(hWnd,0,TRUE);
			free2(300);
			break;
		case IDC_RANDOM3:
			random3Draw=true;
			IndNod=0;
			QueryPerformanceCounter(&t5);
			kil=Random3();
			QueryPerformanceCounter(&t6);
			elapsedTime3 = (t6.QuadPart - t5.QuadPart) * 1000.0 / frequency.QuadPart;
			swprintf(c3,L"%f",elapsedTime3);
			InvalidateRect(hWnd,0,TRUE);
			free2(500);
			break;
		case IDC_EXEMPLU:
			InvalidateRect(hWnd,0,TRUE);
			CreateNods();
			break;
		case IDC_PREFLUX:
			if(IndNod==0)
			{
				mbstowcs(c3,"Nu ati introdus nici un oras!",32);
				MessageBox(NULL, c3 , L"Eroare!",MB_ICONERROR | MB_OK);

				break;
			}
			kil=RealPreflow(sursa,dest,IndNod);
			kil=graf[0].y;
			itoa(kil,c4,10);
			mbstowcs(c1,c4,20);;
			MessageBox(NULL, c1 , L"Succes!",MB_OK);

			break;
		case IDC_SURSA:
			DialogBox(hInst,MAKEINTRESOURCE(IDD_DIALOG3),hWnd,SursaDestinatie);
			break;
		case IDC_ADAUGA_MUCHIE:
			bDrawNod=true;
			bAdaugaMuchie=true;
			DialogBox(hInst,MAKEINTRESOURCE(IDD_DIALOG2),hWnd,Muchie);
			InvalidateRect(hWnd,0,TRUE);
			break;
		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
		}
		break;
	case WM_PAINT:
		hdc = BeginPaint(hWnd, &ps);
			for(int i=0;i<IndNod;i++){
					muchieCant *aux=(muchieCant*)malloc(sizeof(muchieCant));
					aux=graf[i].p;
					while(aux!=NULL){
						for(int j=0;j<IndNod;j++){
							if(strcmp(aux->c,graf[j].nume)==0){
								DrawLine(hdc,graf[i].x,graf[i].y,graf[j].x,graf[j].y,aux->cant);
							}
						}
					aux=aux->next;
					}
				DrawCity(hdc,graf[i].x,graf[i].y,graf[i].nume);
			}
			
				if(random1Draw==true)
					for(int i=0;i<10;i++){
						DrawGraph(hdc,1300+(i*10),800,1300+(i*10),800-(int)(elapsedTime1),c1,255,0,0);
						if(i==9){
							TextOut (hdc,1300,800-(int)(elapsedTime1),c1,wcslen (c1));
							TextOut (hdc,1300,800-(int)(elapsedTime1)+20,L"100 noduri",wcslen (L"100 noduri"));
					}
				}
				if(random2Draw==true){
					for(int i=0;i<10;i++){
						DrawGraph(hdc,1450+(i*10),800,1450+(i*10),800-(int)(elapsedTime2/10),c2,0,255,0);
						if(i==9){
							TextOut (hdc,1450,800-(int)(elapsedTime2/10),c2,wcslen (c2));
							TextOut (hdc,1450,800-(int)(elapsedTime2/10)+20,L"300 noduri",wcslen (L"300 noduri"));
					}
				}	
				
				}

				if(random3Draw==true){
					for(int i=0;i<10;i++){
						DrawGraph(hdc,1600+(i*10),800,1600+(i*10),800-(int)(elapsedTime3/10),c3,0,0,255);
						if(i==9){
							TextOut (hdc,1600,800-(int)(elapsedTime3/10),c3,wcslen (c3));
							TextOut (hdc,1600,800-(int)(elapsedTime3/10)+20,L"500 noduri",wcslen (L"500 noduri"));
					}
				}	
				
				}
			
		EndPaint(hWnd, &ps);
		break;
	case WM_DESTROY:
		PostQuitMessage(0);
		break;
	default:
		return DefWindowProc(hWnd, message, wParam, lParam);
	}
	return 0;
}

// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}

INT_PTR CALLBACK NumeOras(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		if( LOWORD(wParam) ==IDOK)
		{
			TCHAR aux[30]=L"";
			char buffer[50];
			bool greseala=false;
			GetDlgItemText(hDlg, IDC_EDIT1, aux, 50);
			wcstombs(buffer, aux, 50);
			if(strlen(buffer)==0){
				MessageBox(NULL, L"Nu ati introdus nimic!", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			for(int i=0;i<strlen(buffer);i++)
				if(isdigit(buffer[i]))
					greseala=true;
			if(greseala){
				MessageBox(NULL, L"Numele Orasului este introdus gresit", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			strcpy(graf[IndNod].nume,buffer);
			MessageBox(NULL, L"Felicitari ati introdus orasul!", L"Succes!",MB_OK);
			bDrawOras=true;
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}

INT_PTR CALLBACK Muchie(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		if(LOWORD(wParam) == IDOK){
			bool b1Gasit=false,b2Gasit=false,greseala=false;
			int cant=0;
			TCHAR aux1[30]=L"",aux2[30]=L"",aux3[30]=L"";
			char buffer1[50],buffer2[50],buffer3[50];
			GetDlgItemText(hDlg, IDC_EDIT2, aux1, 50);
			GetDlgItemText(hDlg, IDC_EDIT3, aux2 , 50);
			GetDlgItemText(hDlg, IDC_EDIT4, aux3 , 50);
			wcstombs(buffer1, aux1, 50);
			wcstombs(buffer2, aux2 ,50);
			wcstombs(buffer3, aux3 ,50);
			for(int i=0;i<strlen(buffer3);i++)
				if(isalpha(buffer3[i]))
					greseala=true;
			if(greseala){
				MessageBox(NULL, L"Nu ati introdus bine cantitatea", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			cant=atoi(buffer3);
			for(int i=0;i<IndNod;i++){
				if((strcmp(buffer1,graf[i].nume)==0)){
					b1Gasit=true;
					break;
				}
			}
			for(int i=0;i<IndNod;i++){
				if((strcmp(buffer2,graf[i].nume)==0)){
					b2Gasit=true;
					break;
				}
			}


			if(!(b1Gasit&&b2Gasit)){
				MessageBox(NULL, L"Unul dintre orase sau amandoua nu exista", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			else{
				for(int i=0;i<IndNod;i++)
					if(strcmp(buffer1,graf[i].nume)==0){
						muchieCant *nou;
						nou=(muchieCant*)malloc(sizeof(muchieCant));
						strcpy(nou->c,buffer2);
						nou->cant=cant;
						if(graf[i].p==NULL){							
							graf[i].p=nou;
							nou->next=NULL;
						}
						else{
							muchieCant *aux;
							aux=(muchieCant*)malloc(sizeof(muchieCant));
							aux=graf[i].p;
							while(aux!=NULL){
								if(aux->next==NULL){
									aux->next=nou;
									nou->next=NULL;
									break;
								}
								aux=aux->next;
							}
						}
					break;
					}
			}
		EndDialog(hDlg, LOWORD(wParam));
		return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}

INT_PTR CALLBACK SursaDestinatie(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		if( LOWORD(wParam) ==IDOK)
		{
			TCHAR aux[30]=L"",aux1[30]=L"";
			char buffer[50],buffer1[50];
			bool greseala1=false,greseala2=false;
			GetDlgItemText(hDlg, IDC_EDIT5, aux, 50);
			GetDlgItemText(hDlg, IDC_EDIT6, aux1, 50);
			wcstombs(buffer, aux, 50);
			wcstombs(buffer1, aux1, 50);
			for(int i=0;i<strlen(buffer);i++)
				if(isdigit(buffer[i]))
					greseala1=true;
			if(greseala1){
				MessageBox(NULL, L"Numele Orasului este introdus gresit", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			for(int i=0;i<strlen(buffer1);i++)
				if(isdigit(buffer1[i]))
					greseala2=true;
			if(greseala2){
				MessageBox(NULL, L"Numele Orasului este introdus gresit", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			if(strlen(buffer)==0 && strlen(buffer1)==0){
				MessageBox(NULL, L"Nu ati introdus nimic", L"Eroare!",MB_ICONERROR | MB_OK);
				break;
			}
			strcpy(sursa,buffer);
			strcpy(dest,buffer1);
			MessageBox(NULL, L"Felicitari ati introdus sursa si destinatie", L"Succes!",MB_OK);
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}

void DrawCity(HDC hdc,int iPosX,int iPosY,char nume[]){
	wchar_t waCoord[50];
	mbstowcs(waCoord,nume,50);
	TextOut (hdc,iPosX,iPosY,waCoord,wcslen (waCoord));
}

void DrawLine(HDC hdc,int iPosX_1,int iPosY_1,int iPosX_2,int iPosY_2,int cant){
		HPEN hPenOld;
		HPEN hLinePen;
		wchar_t waCant[50];
		char cantaux[10];
		int iPosXaux,iPosYaux;
		itoa(cant,cantaux,10);
		mbstowcs(waCant,cantaux,50);
		iPosXaux=(iPosX_2+iPosX_1)/2;
		iPosYaux=(iPosY_2+iPosY_1)/2;
			
		COLORREF qLineColor;
		qLineColor = RGB(255, 0, 0);
		hLinePen = CreatePen(PS_SOLID, 4, qLineColor);
		hPenOld = (HPEN)SelectObject(hdc, hLinePen);

		MoveToEx(hdc,iPosX_1,iPosY_1,NULL);
		LineTo(hdc,iPosX_2,iPosY_2);
		TextOut (hdc,(iPosXaux+iPosX_2)/2,(iPosYaux+iPosY_2)/2,waCant,wcslen (waCant));
		SelectObject(hdc, hPenOld);
		DeleteObject(hLinePen);	

}


void DrawGraph(HDC hdc,int iPosX_1,int iPosY_1,int iPosX_2,int iPosY_2,TCHAR* c1,int red,int green,int blue){
		HPEN hPenOld;
		HPEN hLinePen;
		COLORREF qLineColor;
		qLineColor = RGB(red, green, blue);
		hLinePen = CreatePen(PS_SOLID, 20, qLineColor);
		hPenOld = (HPEN)SelectObject(hdc, hLinePen);

		MoveToEx(hdc,iPosX_1,iPosY_1,NULL);
		LineTo(hdc,iPosX_2,iPosY_2);
		SelectObject(hdc, hPenOld);
		DeleteObject(hLinePen);	

}


void InitInaltime(char s[32],int k)
{
	for(int i=0;i<=k;i++)
	{
		graf[i].h=0;
		graf[i].e=0;
		if(strcmp(graf[i].nume,s)==0)
			graf[i].h=k;
	}
}

int SearchIndice(char vf[32],int k)// returneaza al catelea este nodul cautat in vectorul Graf
{
	for(int i=0;i<=k;i++)
		if(strcmp(graf[i].nume,vf)==0)
			return i;
}

bool SearchMuchie(nod nd,char d[32],int k)// returneaza true daca exista muchie intre nodul curent si nodul cu numele vfd, false altfel
{
	int i=SearchIndice(nd.nume,k);
	while(nd.p!=NULL)
	{
		if(strcmp(nd.p->c,d)==0)
			return true;
		nd.p=nd.p->next;
	}
	return false;
}

int CostMinim(char s[32],char d[32],int k)// returneaza cantitatea minima pentru muchia dintre nodul s si d
{
	int n=99999,m=99999;
	int q=SearchIndice(s,k);
	muchieCant *aux=graf[q].p;
	while(graf[q].p!=NULL)
	{
		if(strcmp(graf[q].p->c,d)==0)
			n=graf[q].p->cant;
		graf[q].p=graf[q].p->next;
	}
	graf[q].p=aux;
	int b=SearchIndice(d,k);
	muchieCant *aux2=graf[b].p;
	while(graf[b].p!=NULL)
	{
		if(strcmp(graf[b].p->c,s)==0)
			m=graf[b].p->cant;
		graf[b].p=graf[b].p->next;
	}
	graf[b].p=aux2;
	if(n<m)
		return n;
	else
		return m;
}

void InitializarePref(char s[32],int k)// pompeaza flux in vecinii sursei pana la umplerea muchiilor
	// se va respecta simetria muchiilor
{
	int a=SearchIndice(s,k);
	muchieCant *aux=graf[a].p;
	while(graf[a].p!=NULL)
	{
		int b=SearchIndice(graf[a].p->c,k);
		int nr=CostMinim(graf[a].nume,graf[a].p->c,k);
		graf[a].p->flux=nr;
		graf[b].e=graf[a].p->flux;
		graf[a].p=graf[a].p->next;
	}
	graf[a].p=aux;
}

void Pompare(char u[32],char v[32],int k)// pompeaza fluxul in exces(e(u)>0)
	// are loc doar daca diferenta de inaltime dintre u si v este 1
	// (h(u)=h(v)+1), altfel NU ESTE ARC REZIDUAL SI NU NE INTERESEAZA
{
	int d;
	int b=SearchIndice(u,k);
	muchieCant *aux=graf[b].p;
	while(graf[b].p!=NULL)
	{
		if(strcmp(graf[b].p->c,v)==0)
		{
			if(graf[b].e<graf[b].p->cant)
				d=graf[b].e;
			else
				d=graf[b].p->cant;
			graf[b].p->flux = graf[b].p->flux + d;
			graf[b].e = graf[b].e - d;
			int c=SearchIndice(graf[b].p->c,k);
			graf[c].e = graf[c].e + d;
		}
		graf[b].p=graf[b].p->next;
	}
	graf[b].p=aux;
}

void Inaltare(char u[32],int k)// mareste inaltimea lui u daca are flux in exces
{
	int min=k+1;
	int b=SearchIndice(u,k);
	muchieCant *aux=graf[b].p;
	while(graf[b].p!=NULL)
	{
		 int c=SearchIndice(graf[b].p->c,k);
		 if(graf[c].h<min)
			 min=graf[c].h;
		 graf[b].p=graf[b].p->next;
	}
	graf[b].p=aux;
	graf[b].h = 1 + min;
}

void PomparePref(char s[32],char d[32],int k)
{
	int a=SearchIndice(s,k);
	while(graf[a].p!=NULL)
	{
		int b=SearchIndice(graf[a].p->c,k);
		if(graf[a].e>0 && graf[a].h==graf[b].h)
			Inaltare(graf[a].nume,k);
		if(graf[a].h > graf[b].h)
			Pompare(graf[a].nume,graf[b].nume,k);
		graf[a].p=graf[a].p->next;
	}
}

int RealPreflow(char s[32],char d[32],int k)
{
	InitInaltime(s,k);
	InitializarePref(s,k);
	for(int i=0;i<=k;i++)
	{
		if(strcmp(graf[i].nume,d)==0)
			return graf[i].e;
		if(strcmp(graf[i].nume,s)!=0)
			PomparePref(graf[i].nume,d,k);
	}
	int a=SearchIndice(d,k);
	return graf[a].e;
}

void CreareMuchii(int p)
{
	int n;
	for(int i=0;i<p;i++)
	{
		strcpy(graf[i].nume,vec[i]);
		graf[i].e=0;
		n=rand()%80 + p - 81;
		for(int j=0;j<n;j++)
		{
			int a=rand()%80 + p - 85;
			int l=n%a + 1;
			if(strcmp(graf[i].nume,graf[j].nume)==0)
				j=j+1;
			muchieCant *aux2;
			aux2=(muchieCant*)malloc(sizeof(muchieCant));
			strcpy(aux2->c,vec[l]);
			aux2->cant=p%a + 1;
			aux2->flux=0;
			aux2->next=NULL;
			if(graf[i].p==NULL)
				graf[i].p=aux2;
			else
			{
				muchieCant *aux;
				aux=(muchieCant*)malloc(sizeof(muchieCant));
				aux->flux=0;
				aux=graf[i].p;
				while(aux!=NULL)
				{
					if(aux->next==NULL)
					{
						aux->next=aux2;
						aux2->next=NULL;
					}
					aux=aux->next;
				}
			}
		}
	}
}

int CitireRandom(int b)
{
	int i=0;
	char v[32];
	for(int k=1;k<=b;k++)
	{
		itoa(k,v,10);
		strcpy(vec[i++],v);
	}
	return i-2;
}

int Random1()
{
	strcpy(sursa,"1");
	strcpy(dest,"60");
	for(int i=0;i<100;i++)
		vec[i]=(char*)malloc(32*sizeof(char));

	int n=CitireRandom(100);
	CreareMuchii(n);
	int Pref=RealPreflow(sursa,dest,n);
	return Pref;
}

int Random2()
{

	strcpy(sursa,"1");
	strcpy(dest,"260");
	for(int i=0;i<300;i++)
		vec[i]=(char*)malloc(32*sizeof(char));
	
	int n=CitireRandom(300);
	CreareMuchii(n);
	int Pref=RealPreflow(sursa,dest,n);
	return Pref;
}

int Random3()
{

	strcpy(sursa,"1");
	strcpy(dest,"460");
	for(int i=0;i<500;i++)
		vec[i]=(char*)malloc(32*sizeof(char));

	int n=CitireRandom(500);
	CreareMuchii(n);
	int Pref=RealPreflow(sursa,dest,n);
	return Pref;
}

void free1()
{
	for(int i=0;i<IndNod;i++)
	{
		muchieCant *aux=(muchieCant*)malloc(sizeof(muchieCant)),*aux1;
		aux=graf[i].p;
		while(aux!=NULL)
		{
			aux1=aux->next;
			aux->cant=0;
			aux->flux=0;
			free(aux);
			aux=aux1;
		}
		strcpy(graf[i].nume," ");
		graf[i].e=0;
		graf[i].h=0;
		graf[i].x=0;
		graf[i].y=0;
	}
	IndNod=0;

}

void free2(int n){
	
	for(int i=0;i<n;i++){
		free(vec[i]);
	}

}


void CreateMuc(char d[32],int k,int r)
{
	muchieCant *aux2;
	aux2=(muchieCant*)malloc(sizeof(muchieCant));
	strcpy(aux2->c,d);
	aux2->cant=k;
	aux2->flux=0;
	aux2->next=NULL;
	if(graf[r].p==NULL)
		graf[r].p=aux2;
	else
	{
		muchieCant *aux;
		aux=(muchieCant*)malloc(sizeof(muchieCant));
		aux->flux=0;
		aux=graf[r].p;
		while(aux!=NULL)
		{
			if(aux->next==NULL)
			{
				aux->next=aux2;
				aux2->next=NULL;
			}
			aux=aux->next;
		}
	}
}

void CreateNods()
{
	strcpy(sursa,"Arad");
	strcpy(dest,"Oradea");
	IndNod=5;
	strcpy(graf[0].nume,"Arad");//422,131
	graf[0].x=422;
	graf[0].y=131;
	strcpy(graf[1].nume,"Deva");//755,45
	graf[1].x=755;
	graf[1].y=45;
	strcpy(graf[2].nume,"Timisoara");//901,148
	graf[2].x=901;
	graf[2].y=148;
	strcpy(graf[3].nume,"Oradea");//893,397
	graf[3].x=893;
	graf[3].y=397;
	strcpy(graf[4].nume,"Bihor");//530,411
	graf[4].x=530;
	graf[4].y=411;
	CreateMuc("Deva",20,0);
	CreateMuc("Oradea",45,0);
	CreateMuc("Timisoara",17,0);
	CreateMuc("Bihor",66,1);
	CreateMuc("Arad",39,3);
	CreateMuc("Timisoara",89,4);
	CreateMuc("Oradea",11,4);
}